Cạnh(Edge): Cạnh nối đỉnh x với đỉnh y là một tập gồm hai phần tử {x,y}, thường được vẽ dưới dạng một đoạn thẳng nối hai đỉnh. Cạnh nối hai đỉnh x và y được ký hiệu là xy (không phải x⋅y). Tập cạnh của G thường được ký hiệu là E(G), hoặc E nếu không có nguy cơ hiểu nhầm.
Cạnh có hướng là một cặp đỉnh có thứ tự. Trong mỗi cặp có thứ tự đó, đỉnh thứ nhất được gọi là đỉnh đầu, đỉnh thứ hai là đỉnh cuối. Cạnh vô hướng không quan tâm đến hướng và coi hai đỉnh như nhau.
Cạnh lá: Cạnh nối với một đỉnh lá.
Cạnh cắt: xem Cầu.
Cạnh kề nhau : Hai cạnh của một đồ thị được xem là kề nhau nếu chúng có một đỉnh chung.
Cặp ghép: (matching): một cặp ghép M của đồ thị G = (V,E) là một tập các cạnh đôi một không kề nhau của G.
Cặp ghép hoàn hảo (perfect matching): là cặp ghép phủ tất cả các đỉnh của đồ thị. Nghĩa là mỗi đỉnh của đồ thị đều liên thuộc với đúng một cạnh của cặp ghép.
Cặp ghép lớn nhất, Cặp ghép tối đa: là cặp ghép chứa nhiều cạnh nhất có thể. Có thể có nhiều cặp ghép tối đa.
Cấp (order) của một đồ thị là số đỉnh của nó, nghĩa là |V(G)|.
Cầu: là một cạnh mà nếu loại bỏ nó thì đồ thị tăng số thành phần liên thông.
Cây bao trùm(cây khung): là một đồ thị con bao trùm có dạng cây. Chỉ có đồ thị liên thông mới có cây bao trùm.
Cây (có gốc): thường được coi như các đồ thị đơn có hướng phi chu trình với các cung hướng từ phía gốc ra phía lá. Với mỗi cung, đỉnh tại gốc cung được gọi là đỉnh cha hoặc cha, các đỉnh tại điểm cuối của cung được gọi là đỉnh con hoặc con của đỉnh tại gốc cung.
Cây con: một cây con của đồ thị G là một đồ thị con có dạng cây.
Cây k-ary:(ví dụ: nhị phân, tam phân...) là cây có gốc mà mỗi đỉnh trong đều có không quá k con.
Cây đơn phân chỉ là một đường đi.Cây nhị phân là cây mà mỗi đỉnh có không quá 2 con.Cây nhị phân đầy đủ là cây mà mỗi đỉnh trong có đúng 2 con.
Chỉ số clique: Chỉ số clique ω(G) của đồ thị G là bậc của đồ thị con đầy đủ lớn nhất của G.
Chỉ số độc lập: Chỉ số độc lập của đồ thị G, ký hiệu α(G), là kích thước của tập độc lập lớn nhất của G.
Chu trình trong đồ thị: là một đường đi đóng trong đồ thị. Đồ thị chỉ gồm một chu trình với n đỉnh được gọi là đồ thị vòng, ký hiệu Cn,
Chu trình có hướng: là một chu trình đơn mà mọi cung trong đó đều cùng hướng, nghĩa là mọi đỉnh đều có bậc trong và bậc ngoài bằng 1. Có thể gọi đơn giản là chu trình khi ngữ cảnh rõ ràng.
Chu trình đơn: là chu trình đi qua mỗi đỉnh không quá một lần. Trong đồ thị ở hình trên, (1, 5, 2, 1) là một chu trình đơn. Nếu không chỉ rõ, chu trình thường được hiểu là một chu trình đơn.
Chu trình Euler: là chu trình qua tất cả các cạnh, mỗi cạnh đúng một lần.
Chu trình lẻ: là chu trình có độ dài lẻ.
Chu vi nhỏ (girth): Chu vi nhỏ của một đồ thị là độ dài của chu trình đơn ngắn nhất của đồ thị.
Chu vi lớn (circumference): Chu vi lớn của một đồ thị là độ dài của chu trình đơn dài nhất của đồ thị. Đối với đồ thị không có chu trình, chu vi lớn và chu vi nhỏ được định nghĩa bằng giá trị vô cùng ∞.
Chuỗi bậc (degree sequence): là danh sách các bậc của một đồ thị sắp xếp theo thứ tự giảm dần. (ví dụ, d1 ≥ d2 ≥ … ≥ dn). Một chuỗi giảm dần các số tự nhiên được coi là hiện thực được (realizable) nếu nó là chuỗi bậc của một đồ thị nào đó.
